﻿//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Core.h".
//-------------------------------------------------------------------

#ifndef _UXS_QUEUE_TYPE_H
#define _UXS_QUEUE_TYPE_H

#pragma once

#include "TArray.h"

namespace UX_STL
{
namespace UXTypes
{

	#define RET_ERROR( _ret )	{ WARNING("error in queue");  return _ret; }
	#define RET_FALSE			RET_ERROR( false )
	#define RET_VOID			RET_ERROR( ; )



	//
	// Queue
	//
	
	#define TQueue		queue

	template <	typename T,
				typename S = TCopyStrategy<T>,
				typename A = TAllocator<T>
			 >
	class TQueue
	{
	// types
	public:
		typedef TMemoryViewer<T>		vis_mem_t;
		typedef S						Strategy;
		typedef A						Allocator;
		typedef T						value_t;
		typedef TQueue<T,S,A>			Self;
		typedef uni_array<T>			uni_arr;
		typedef uni_array<const T>		uni_c_arr;
		

	// variables
	private:
		union {
			T		*	_pMemory;
			vis_mem_t	_pVisible;
		};
		isize			_uFirst,
						_uLast,
						_uSize;

		//  __________ _____________ __________
		// | reserved | used memory | reserved |
		// 0       _uFirst       _uLast      _uSize
		

	// methods
	private:
		void _Reallocate (usize uNewSize);
		void _ReplaceToLeft (usize uOffset = 1);
		void _ReplaceToRight (usize uOffset = 1);

		template <typename B>	void _Copy (B *pArray, usize uCount);
		
		static usize _CalcFirstOffset (usize uSize);
		static usize _GetNewSize (usize uNewSize);

	public:
		TQueue ();

		explicit
		TQueue (usize uSize);

		TQueue (const Self &sQueue);

		RVALUE_REFERENCE_ONLY( TQueue (Self &&sQueue); )

		TQueue (uni_c_arr sArray);

		~TQueue ()										{ Clear(); }

		T		*	ptr ();
		T const	*	ptr () const;

		T		&	Front ();
		T const	&	Front () const;

		T		&	Back ();
		T const	&	Back () const;

		bool		operator ! () const					{ return not Empty(); }
		
		operator		uni_arr ()						{ return uni_arr( _pMemory + _uFirst, Count() ); }
		operator const	uni_c_arr () const				{ return uni_c_arr( _pMemory + _uFirst, Count() ); }

		T		&	operator [] (usize i);
		T const	&	operator [] (usize i) const;

		Self &		operator << (const T& tValue)		{ PushBack( tValue );   return *this; }
		Self &		operator << (uni_arr a)				{ AppendBack( a );		return *this; }

		friend Self &	operator >> (const T& left, Self &right)	{ right.PushFront( left );	 return right; }
		friend Self &	operator >> (uni_arr left, Self &right)		{ right.AppendFront( left ); return right; }

		Self &		operator =  (const Self &a)			{ Copy( a );  return *this; }
		Self &		operator =  (uni_arr a)				{ Copy( a );  return *this; }

		void PushBack (const T &tValue);
		void PushBack (INOUT T& tValue);
		RVALUE_REFERENCE_ONLY( void PushBack (T&& tValue); )

		void PushFront (const T &tValue);
		void PushFront (INOUT T& tValue);
		RVALUE_REFERENCE_ONLY( void PushFront (T&& tValue); )

		void PopBack ();
		void PopFront ();

		void Resize (usize uNewSize);
		void Reserve (usize uSize);

		void Clear ();
		void ClearMem ();

		void Copy (uni_c_arr sArray);
		void Copy (uni_arr sArray);

		void AppendFront (uni_c_arr sArray);
		void AppendFront (uni_arr sArray);
		
		void AppendBack (uni_c_arr sArray);
		void AppendBack (uni_arr sArray);

		void Erase (usize uPos, usize uCount);
		void EraseFromFront (usize uCount);
		void EraseFromBack (usize uCount);
		
		void SwapMem (INOUT Self &sQueue);
		void SetMem (INOUT Self &sQueue);

		usize		Count ()	 const				{ return Empty() ? 0 : _uLast - _uFirst + 1; }
		usize		Size ()		 const				{ return sizeof(T) * Count(); }
		usize		Capacity ()	 const				{ return _uSize; }
		usize		FullSize ()	 const				{ return sizeof(T) * _uSize; }
		bool		Empty ()	 const				{ return /*_uLast == -1 or*/ _uFirst > _uLast; }
		usize		LastIndex () const				{ return Count()-1; }
	};



	template <typename T, typename S, typename A>
	inline TQueue<T,S,A>::TQueue () : _pMemory(null), _uSize(0), _uFirst(0), _uLast(-1) {}

	
	template <typename T, typename S, typename A>
	inline TQueue<T,S,A>::TQueue (usize uSize) : _pMemory(null), _uSize(0), _uFirst(0), _uLast(-1)
	{
		_Reallocate( uSize );
	}
	
		
	template <typename T, typename S, typename A>
	inline TQueue<T,S,A>::TQueue (const Self &sQueue) : _pMemory(null), _uSize(0), _uFirst(0), _uLast(-1)
	{
		Copy( sQueue );
	}
	

	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline TQueue<T,S,A>::TQueue (Self &&sQueue) : _pMemory(null), _uSize(0), _uFirst(0), _uLast(-1)
		{
			SetMem( sQueue );
		}
	)


	template <typename T, typename S, typename A>
	inline TQueue<T,S,A>::TQueue (uni_c_arr sArray) : _pMemory(null), _uSize(0), _uFirst(0), _uLast(-1)
	{
		Copy( sArray );
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::_Reallocate (usize uNewSize)
	{
		usize	u_old_first	= _uFirst,
				u_old_count	= Count(),
				u_count		= uNewSize < u_old_count ? uNewSize : u_old_count;
		T	*	p_old		= _pMemory;

		_uSize				= _GetNewSize( uNewSize );
		_pMemory			= Allocator::Allocate( _uSize );
		_uFirst				= _CalcFirstOffset( _uSize );
		_uLast				= _uFirst + u_count - 1;

		if ( p_old == null ) {
			return;
		}

		Strategy::Replace( _pMemory + _uFirst, p_old + u_old_first, u_count );

		if ( u_count < u_old_count )
			Strategy::Destroy( p_old + u_old_first + u_old_count, u_old_count - u_count );

		Allocator::Deallocate( p_old );
	}
	
	
	template <typename T, typename S, typename A>
	inline usize TQueue<T,S,A>::_CalcFirstOffset (usize uSize)
	{
		const usize	nom	= CoreTypesConfig::QueueResizingNominator;
		const usize	den	= CoreTypesConfig::QueueResizingDenominator;
		return (uSize * nom + den*2 - 1) / (den * 2);
	}

	
	template <typename T, typename S, typename A>
	inline usize TQueue<T,S,A>::_GetNewSize (usize uNewSize)
	{
		const usize	nom		 = CoreTypesConfig::QueueResizingNominator;
		const usize	den		 = CoreTypesConfig::QueueResizingDenominator;
		const usize	min_size = CoreTypesConfig::QueueResizingMinSize;
		const usize	temp	 = (uNewSize * nom + den - 1) / den;
		return ( uNewSize + (temp < min_size ? min_size : temp) );
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::_ReplaceToLeft (usize uOffset)
	{
		if ( _uLast + (isize)uOffset < _uSize ) {
			_uLast += uOffset;
			return;
		}
		
		const usize	u_first = _CalcFirstOffset( _uSize + uOffset );

		if ( isize(u_first + CoreTypesConfig::QueueResizingMinSize) < _uFirst )
		{
			for (usize i = 0; i < Count(); ++i)
				Strategy::Replace( _pMemory + u_first + i, _pMemory[_uFirst + i] );

			_uLast -= _uFirst - u_first;
			_uFirst = u_first;
			return;
		}

		_uLast += uOffset;
		_Reallocate( _uSize + uOffset );
	}


	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::_ReplaceToRight (usize uOffset)
	{
		if ( _uFirst > isize(uOffset + 1) ) {
			_uFirst -= uOffset;
			return;
		}

		const usize	u_first = _CalcFirstOffset( _uSize + uOffset );

		if ( isize(u_first + Count()) > _uLast + CoreTypesConfig::QueueResizingMinSize )
		{
			for (isize i = Count()-1; i >= 0; --i)
				Strategy::Replace( _pMemory + u_first + i, _pMemory[_uFirst + i] );

			_uLast += u_first - _uFirst;
			_uFirst = u_first;
			return;
		}

		_uFirst -= uOffset;
		_Reallocate( _uSize + uOffset );
	}

	
	template <typename T, typename S, typename A>
	template <typename B>
	inline void TQueue<T,S,A>::_Copy (B *pArray, usize uCount)
	{
		ClearMem();

		if ( pArray == null or uCount == 0 )
			RET_VOID;
		
		ASSERT( pArray < _pMemory and pArray >= _pMemory + _uSize );
		
		const usize	nom			= CoreTypesConfig::QueueResizingNominator;
		const usize	den			= CoreTypesConfig::QueueResizingDenominator;
		const usize	u_new_size	= uCount + ((uCount * nom + den - 1) / den);

		if ( u_new_size < _uSize )
		{
			_uSize = u_new_size;
			Allocator::Deallocate( _pMemory );
			_pMemory = Allocator::Allocate( _uSize );
		}

		_uFirst  = _CalcFirstOffset( _uSize );
		_uLast	 = _uFirst + uCount;

		Strategy::Copy( _pMemory + _uFirst, pArray, uCount );
	}
	

	template <typename T, typename S, typename A>
	inline T & TQueue<T,S,A>::operator [] (usize uNumb)
	{
		ASSERT( uNumb < Count() );
		return _pMemory[ uNumb + _uFirst ];
	}

	
	template <typename T, typename S, typename A>
	inline const T & TQueue<T,S,A>::operator [] (usize uNumb) const
	{
		ASSERT( uNumb < Count() );
		return _pMemory[ uNumb + _uFirst ];
	}

	
	template <typename T, typename S, typename A>
	inline T * TQueue<T,S,A>::ptr ()
	{
		ASSUME( _pMemory != null and _uFirst < _uSize );
		return _pMemory + _uFirst;
	}


	template <typename T, typename S, typename A>
	inline const T * TQueue<T,S,A>::ptr () const
	{
		ASSUME( _pMemory != null and _uFirst < _uSize );
		return _pMemory + _uFirst;
	}


	template <typename T, typename S, typename A>
	inline T & TQueue<T,S,A>::Front ()
	{
		ASSUME( _pMemory != null and _uFirst < _uSize );
		return _pMemory[_uFirst];
	}


	template <typename T, typename S, typename A>
	inline const T & TQueue<T,S,A>::Front () const
	{
		ASSUME( _pMemory != null and _uFirst < _uSize );
		return _pMemory[_uFirst];
	}


	template <typename T, typename S, typename A>
	inline T & TQueue<T,S,A>::Back ()
	{
		ASSUME( _pMemory != null and _uLast < _uSize );
		return _pMemory[_uLast];
	}


	template <typename T, typename S, typename A>
	inline const T & TQueue<T,S,A>::Back () const
	{
		ASSUME( _pMemory != null and _uLast < _uSize );
		return _pMemory[_uLast];
	}
	
	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::PushBack (const T &tValue)
	{
		_ReplaceToLeft();
		Strategy::Construct( _pMemory + _uLast, tValue );
	}
	
	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::PushBack (T &tValue)
	{
		_ReplaceToLeft();
		Strategy::Construct( _pMemory + _uLast, tValue );
	}
	

	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline void TQueue<T,S,A>::PushBack (T &&tValue)
		{
			_ReplaceToLeft();
			Strategy::Construct( _pMemory + _uLast, ToRValueRef( tValue ) );
		}
	)

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::PushFront (const T &tValue)
	{
		_ReplaceToRight();
		Strategy::Construct( _pMemory + _uFirst, tValue );
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::PushFront (T &tValue)
	{
		_ReplaceToRight();
		Strategy::Construct( _pMemory + _uFirst, tValue );
	}


	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline void TQueue<T,S,A>::PushFront (T &&tValue)
		{
			_ReplaceToRight();
			Strategy::Construct( _pMemory + _uFirst, ToRValueRef( tValue ) );
		}
	)

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::PopBack ()
	{
		if ( _uFirst <= _uLast ) {
			Strategy::Destruct( _pMemory + _uLast );
			--_uLast;
		}
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::PopFront ()
	{
		if ( _uFirst <= _uLast ) {
			Strategy::Destruct( _pMemory + _uFirst );
			++_uFirst;
		}
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::Resize (usize uNewSize)
	{
		usize	u_old = Count();
		_Reallocate( uNewSize );

		TODO( "need create objects" );
		/*if ( Count() > u_old )
			Strategy::Create( _pMemory +*/
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::Reserve (usize uSize)
	{
		if ( (isize)uSize <= _uSize )
			return;

		_Reallocate( uSize );
	}
	

	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::SwapMem (TQueue<T,S,A> &sQueue)
	{
		usize	temp;

		_swap( this->_pMemory,	sQueue._pMemory,	ReferenceCast<T *>(temp) );
		_swap( this->_uFirst,	sQueue._uFirst,		temp );
		_swap( this->_uLast,	sQueue._uLast,		temp );
		_swap( this->_uSize,	sQueue._uSize,		temp );
	}
	

	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::SetMem (Self &sQueue)
	{
		Clear();

		_pMemory = sQueue._pMemory;
		_uFirst	 = sQueue._uFirst;
		_uLast	 = sQueue._uLast;
		_uSize	 = sQueue._uSize;

		sQueue._pMemory = null;
		sQueue._uFirst	= 0;
		sQueue._uLast	= 0;
		sQueue._uSize	= 0;
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::Clear ()
	{
		if ( _pMemory != null ) {
			Strategy::Destroy( _pMemory + _uFirst, Count() );
			Allocator::Deallocate( _pMemory );
		}
		_uFirst = 0;
		_uSize	= 0;
		_uLast	= -1;
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::ClearMem ()
	{
		if ( _pMemory != null ) {
			Strategy::Destroy( _pMemory + _uFirst, Count() );
			Strategy::ZeroMem( _pMemory, _uSize );
		}
		_uFirst	= _CalcFirstOffset( _uSize );
		_uLast	= _uFirst-1;
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::Copy (uni_c_arr sArray)
	{
		return _Copy<const T>( sArray.ptr(), sArray.Count() );
	}

	
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::Copy (uni_arr sArray)
	{
		return _Copy<T>( sArray.ptr(), sArray.Count() );
	}
		

	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::AppendFront (uni_c_arr sArray)
	{
		if ( sArray.Empty() )
			return;

		_ReplaceToRight( sArray.Count() );
		Strategy::Copy( _pMemory + _uFirst, sArray.ptr(), sArray.Count() );
	}
		

	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::AppendFront (uni_arr sArray)
	{
		if ( sArray.Empty() )
			return;

		_ReplaceToRight( sArray.Count() );
		Strategy::Copy( _pMemory + _uFirst, sArray.ptr(), sArray.Count() );
	}
		
		
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::AppendBack (uni_c_arr sArray)
	{
		if ( sArray.Empty() )
			return;

		_ReplaceToLeft( sArray.Count() );
		Strategy::Copy( _pMemory + _uLast - sArray.Count() + 1, sArray.ptr(), sArray.Count() );
	}
		
		
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::AppendBack (uni_arr sArray)
	{
		if ( sArray.Empty() )
			return;

		_ReplaceToLeft( sArray.Count() );
		Strategy::Copy( _pMemory + _uLast - sArray.Count() + 1, sArray.ptr(), sArray.Count() );
	}

	
		
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::Erase (usize uPos, usize uCount)
	{
		const usize		u_count = Count();

		if ( uPos >= u_count or uCount == 0 or u_count == 0 )
			RET_VOID;

		if ( uPos + uCount >= u_count )
			uCount = u_count - uPos;

		if ( uPos <= (u_count - uPos - uCount) )
		{
			// erase from left
			Strategy::Destroy( _pMemory + _uFirst + uPos, uCount );
			Strategy::Replace( _pMemory + _uFirst + uPos, _pMemory + _uFirst, uPos );
			_uFirst += uCount;
		}
		else
		{
			// erase from right
			Strategy::Destroy( _pMemory + _uFirst + uPos, uCount );
			Strategy::Replace( _pMemory + _uFirst + uPos, _pMemory + _uLast - uPos - uCount, u_count - uPos - uCount );
			_uLast -= uCount;
		}
	}

		
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::EraseFromFront (usize uCount)
	{
		return Erase( 0, uCount );
	}

		
	template <typename T, typename S, typename A>
	inline void TQueue<T,S,A>::EraseFromBack (usize uCount)
	{
		ASSERT( uCount < Count() );
		return Erase( Count() - uCount, uCount );
	}


	#undef  TQueue
	#undef  RET_ERROR
	#undef  RET_FALSE
	#undef  RET_VOID

//-------------------------------------------------------------------

}	// ECType
}	// UX_STL

#endif	// _UXS_QUEUE_TYPE_H